首页 > 试题广场 >

在旋转过的有序数组中寻找目标值

[编程题]在旋转过的有序数组中寻找目标值
  • 热度指数：41149 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
有一个长度为 n 的按严格升序排列的整数数组 nums ，在实行 search 函数之前，在某个下标 k 上进行旋转，使数组变为[nums[k],nums[k+1],.....,nums[nums.length-1],nums[0],nums[1],.......,nums[k-1]]。
给定旋转后的数组 nums 和一个整型 target ，请你查找 target 是否存在于 nums 数组中并返回其下标（从0开始计数），如果不存在请返回-1。

数据范围：
要求：空间复杂度 ，时间复杂度

比如，数组[0,2,4,6,8,10]在下标3处旋转之后变为[6,8,10,0,2,4], 当给定target为10时，10的下标是2，target为3时，nums数组中不存在3，所以返回-1


示例1

输入

[6,8,10,0,2,4],10

输出

2

说明

如题面解释
示例2

输入

[6,8,10,0,2,4],3

输出

-1

说明

如题面解释
示例3

输入

[2],1

输出

-1

备注:
1 <= nums.length <= 4000
算法知识视频讲解
添加回答
Python 3
来牛客玩玩头像 来牛客玩玩 
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        # write code here
        left, right = 0, len(nums)-1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            # 左半部分有序
            if nums[mid] >= nums[left]:
                if target > nums[mid]:
                    left = mid+1
                else:
                    if nums[left] == target:
                        return left
                    elif nums[left] > target:
                        left = mid+1
                    else:
                        right = mid-1
            # 右半部分有序
            else:
                if target < nums[mid]:
                    right = mid-1
                else:
                    if nums[right] == target:
                        return right
                    elif nums[right] < target:
                        right = mid-1
                    else:
                        left = mid+1
        return -1

发表于 2022-07-26 20:43:14 回复(0)
Python 3
danspace头像 danspace 
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        # write code here
        if target in nums:
            return nums.index(target)
        return -1

发表于 2022-04-19 12:43:41 回复(0)
Python 3
JSFaner头像 JSFaner 
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        left,right = 0,len(nums)-1
        while left<=right:
            mid = (left+right)//2
            if nums[mid]<target: left = mid+1
            elif nums[mid]>target: right = mid-1
            else: return mid
        return -1

发表于 2021-11-17 21:35:05 回复(0)
Python 3
牛客634691541号头像 牛客634691541号
class Solution:
    def search(self , nums , target ):
        # write code here
        if target in nums:
            n = nums.index(target)
        else:
            n = -1
        return n
            
发表于 2021-08-22 15:29:03 回复(0)
Python 3
蓝猫小哥哥头像 蓝猫小哥哥
利用部分有序性实现二分 

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @param target int整型 
# @return int整型
#
class Solution:
    def search(self , nums , target ):
        # write code here
        '''
        思路明确一点：我们就是要利用旋转数组的 部分有序性 来实现二分查找。
        时间复杂度：O(log(n))，空间复杂度：O(1)
        '''
        left ,right = 0,len(nums)-1
        while left <= right:
            mid = (left+right) >>1
            if nums[mid] == target:return mid
            if nums[mid]  > nums[0]:
                if nums[0] <= target < nums[mid]:
                    right = mid-1
                else:
                    left = mid+1
            else:
                if nums[mid] < target <= nums[-1]:
                    left = mid+1
                else:
                    right = mid-1
        return -1


发表于 2021-07-20 19:13:27 回复(0)
提交观点

问题信息

二分
上传者：牛客301499号
难度：
5条回答 2916浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号